1. Field of the Invention
The present invention relates to a method for resource allocation/analysis and scheduling, and a system therefor designed for optimum allocation of workers or materials in production management, scheduling of the manufacturing process or computing procedures, or layout of logic diagrams or functional charts, etc.
2. Description of the Prior Art
In order to analyze and solve the allocation of resources, scheduling or the maximum flow which can be represented by a network, there have been methods using a graphic theory and a linear programing method.
According to the method using the graphic theory, a concept of a flow is employed with respect to a network, so that the aforementioned kind of problem is analyzed as a problem of the flow. The problem of the maximum flow is one of the flow problems. The flow problem can be analyzed, for example, according to a procedure proposed by Dinic which is disclosed in "Practice of Graphic Theory-Basis and Application-" (1983). According to the method by Dinic, the maximum flow from an entrance to an exit of a network is obtained by repeatedly searching for the shortest incrementable path among allowable flows set for each branch. A flow which occurs when the shortest incrementable path is not present is regarded as the maximum flow.
Meanwhile, according to the linear programming method, the relationship between the inflow and outflow in the whole network or at each node, and the restrictions of the flow rate, etc. at each branch and a corresponding objective function are analyzed by a simplex method revealed in "Guide to Linear Programming Method" (1980). Karmarkar's method is found in Japanese Laid-Open Patent Publication No. 02-244261. The simplex method is the most general method among the linear programming methods, whereby various restrictions in the network are constructed into a model, so that a solution to make the objective function optimum is repeatedly selected so as to thereby obtain the optimum solution while a practicable solution to satisfy the restrictions is set as an initial value. The Karmarkar method was devices to speed-up the linear programming method. Since the efficiency of selecting a solution is increased more than by the simplex method, the number of repetitions until the optimum value is obtained is reduced so much as to obtain the solution in real time. Moreover, even the case where a solution cannot be obtained by the simplex method can be analyzed in accordance with Karmarkar's method.
However, there is a disadvantage in the conventional analyzing method, i.e., the method of Dinic in that as the scale of the network is increased or becomes more complicated due to the repeated operations to search for the incrementable path from the entrance to the exit of the network, more time is required.
When a solution is repeatedly searched or a value of the objective function is calculated, by the simplex method, it is necessary to operate matrices of degrees proportional to the number of the restrictions and therefore, the operating or computing time becomes proportional to a square of the number of the restrictions regardless of the scale of the network. In many cases, it is even impossible to obtain a solution.
On the other hand, although Karmarkar's method realizes high-speed processing nearly in real time, operations of matrices are still necessary and the procedure cannot help but be complicated as a consequence of the enlargement of the scale of the network.